#include<iostream>
#include<queue>
#include<stack>

using namespace std;

/**
* 实现二叉树的创建、遍历6种实现、按层遍历
*/

struct Node{
    int value;
    Node * left;
    Node * right;
};

Node * createBinaryTree(int * data, int length){
    Node * head = new Node();
    head -> value = data[0];
    head -> left = head -> right = nullptr;
    for ( int i = 1 ; i < length ; i++ ){
        Node * node = new Node();
        node -> value = data[i];
        node -> left = node -> right = nullptr;

        Node * pHead = head;
        
        while ( pHead != nullptr ){
            if ( pHead -> value < data[i] ){
                // 进入右孩子, 判断右孩子是否为空
                if ( pHead -> right == nullptr ){
                    pHead -> right = node;
                    break;
                }else {
                    pHead = pHead -> right;
                }
            }else {
                // 进入左孩子
                if ( pHead -> left == nullptr ){
                    pHead -> left = node;
                    break;
                }else {
                    pHead = pHead -> left;
                }
            }
        }
    }
    return head;
}

// 前序递归遍历
void PreOrderTraverse(Node * head){
    if ( head == nullptr ) {
	return;
    }
    cout << head->value << "  ";
    PreOrderTraverse(head->left);
    PreOrderTraverse(head->right);
}

// 循环前序遍历
void PreOrder(Node * root){
    stack<Node *> s;
    s.push(root);
    while ( !s.empty() ){
        // 获取栈首元素
        Node * node = s.top();
        // 出栈
        s.pop();
        cout << node -> value << "  ";
        // 前序遍历：要先入栈右孩子，再入栈左孩子
        if ( node -> right != nullptr ) s.push(node->right);
        if ( node -> left != nullptr ) s.push(node -> left);
    }
}


// 中序递归遍历
void InOrderTraverse(Node * head){
    if ( head == nullptr ) {
	    return;
    }
    InOrderTraverse(head->left);
    cout << head->value << "  ";
    InOrderTraverse(head->right);
}


// 中序非递归遍历
void InOrder(Node * root){
    if ( root == nullptr )
        return;
    // 声明栈
    stack<Node *> s;
    Node * node = root;
    while ( node || !s.empty() ){
        // 如果左孩子不为空则入栈
        while ( node != nullptr ){
            s.push(node);
            node = node -> left;
        }
        
        // 获取栈顶元素
        node = s.top();
        cout << node -> value << "  ";
        // 出栈
        s.pop();
        node = node -> right;
    }
}

// 后序递归遍历
void PostOrderTraverse(Node * head){
    if ( head == nullptr ) {
	    return;
    }
    PostOrderTraverse(head->left);
    PostOrderTraverse(head->right);
    cout << head->value << "  ";
}

// 后续非递归遍历
void PostOrder(Node * root){
    if ( root == nullptr )
        return;
    Node * node = root;
    stack<Node * > s;
    // 记录最后一次访问节点
    Node * last = nullptr;
    while ( node != nullptr || !s.empty() ){
        // 将左节点入栈
        while ( node != nullptr ){
            s.push(node);
            node = node -> left;
        }

        // 获取栈顶元素
        node = s.top();
        // 判断节点右孩子是否为空
        if ( node -> right != nullptr && last != node -> right ){
            node = node -> right;
        }else if ( node -> right == nullptr || last == node -> right ){
            // 右孩子不存在/右孩子已经被访问过
            s.pop();
            cout << node -> value << "  ";
            // 修改访问标记
            last = node;
            // 将node滞空，防止重复将左孩子压栈，避免死循环
            node = nullptr;
        }
    }
}

// 按层遍历
void levelOrder(Node * head){
    queue<Node * > q;
    q.push(head);
    // 判断队列不空
    while ( !q.empty() ){
        // 获取队列首元素
        Node * p = q.front();
        // 出队
        q.pop();
        cout << p -> value << "  ";
        // 元素入队
        if ( p -> left != nullptr ) q.push(p->left);
        if ( p -> right != nullptr ) q.push(p->right);
    }
}

int main(void){
    int length = 7;
    int data[] = {3,4,6,7,2,5,1};
    Node * head = createBinaryTree(data, length);
    cout << "PreOrder: ";
    PreOrderTraverse(head);
    cout << endl << "InOrder: ";
    InOrderTraverse(head);
    cout << endl << "PostOrder: ";
    PostOrderTraverse(head);
    cout << endl << "LevelOrder: ";
    levelOrder(head);
    cout << endl << "PreOrder: ";
    PreOrder(head);
    cout << endl << "InOrder: ";
    InOrder(head);
    cout << endl << "PostOrder: ";
    PostOrder(head);
    cout << endl;
    return 0;
}

// 推荐博客：https://blog.csdn.net/qq_38134165/article/details/79871430